package interview.topk;

import java.util.ArrayList;
import java.util.Comparator;

public class Heap<T> {
	
	Comparator<T> c;
	ArrayList<T> array;
	
	public Heap(ArrayList<T> array, Comparator<T> c) {
		this.array = array;
		this.c = c;
	}
	
	public void buildHeap(boolean ascending) {
		int length = array.size();
		int mid = length / 2;
		for(int i = mid; i >= 0; i--) {
			minheapify(i, length);
		}
	}

	private void minheapify(int index, int length) {
		int smallest = index;
		int left = index * 2 + 1;
		int right = index * 2 + 2;
		
		if(left < length && (c.compare(array.get(index), array.get(left)) == 1))
			smallest = left;
		
		if(right < length && (c.compare(array.get(index), array.get(right)) == 1)) {
			smallest = right;
		} 
		
		if (smallest != index) {
			T buf = array.get(index);
			array.set(index, array.get(smallest));
			array.set(smallest, buf);
			minheapify(smallest, length);
		}
	}
	
	public T min() {
		minheapify(0, array.size());
		return array.get(0);
	}
}
